#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;

class Solution {
private:
    unordered_map<int, int> dp;
    vector<int>* arr2;
    void set_arr2() {
        unordered_set<int> set(arr2->begin(), arr2->end());
        arr2->assign(set.begin(), set.end());
        sort(arr2->begin(), arr2->end());
    }
    int find_arr2_min(int larger_than) {
        int left = 0, right = arr2->size() - 1, mid = (left + right) / 2;
        for (; left < right; ) {
            int mid_num = arr2->at(mid);
            if (larger_than > mid_num) {
                if (left == mid) {
                    if (larger_than >= arr2->at(right)) {
                        right = arr2->size() - 1;
                    } else {
                        right = left;
                    }
                    break;
                }
                left = mid;
                mid = (left + right) / 2;
            } else if (larger_than < mid_num) {
                right = mid;
                mid = (left + right) / 2;
            } else {
                right = mid;
                break;
            }
        }
        if (right == arr2->size() - 1) {
            return -1;
        } else {
            return arr2->at(right + 1);
        }
    }
    void set_dp(int num, int min_step, unordered_map<int, int>* dp) {
        auto item = dp->find(num);
        if (item == dp->end()) {
            dp->insert(pair<int, int> {num, min_step});
        } else {
            item->second = min(min_step, item->second);
        }
    }
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        this->arr2 = &arr2;
        set_arr2();
        if (arr1.size() <= 1) {
            return 0;
        }
        if (arr2[0] == arr1[0]) {
            dp[arr1[0]] = 0;
        } else {
            dp[arr1[0]] = 0;
            dp[arr2[0]] = 1;
        }
        for (int i = 1; i < arr1.size(); i++) {
            unordered_map<int, int> next_dp;
            for (auto item: dp) {
                int num = find_arr2_min(item.first);
                if (num != -1) {
                    set_dp(num, item.second + 1, &next_dp);
                }
                if (item.first < arr1[i]) {
                    set_dp(arr1[i], item.second, &next_dp);
                }
            }
            if (next_dp.size() == 0) {
                return -1;
            }
            dp = next_dp;
        }
        int result = INT32_MAX;
        for (auto item: dp) {
            result = min(item.second, result);
        }
        return result;
    }
};


int main() {
    Solution solution;
    vector<int> input1 = {5,16,19,2,1,12,7,14,5,16};
    vector<int> input2 = {6,17,4,3,6,13,4,3,18,17,16,7,14,1,16};
    int output = solution.makeArrayIncreasing(input1, input2);
    cout << output << endl;
}